package birthtree;

public class Kruskal 
{ 
	public static final int NOT_REACHED = -1; 
	public static void kruskal(int[][] E) { 
		int n = E.length; MinHeap<Edge> edges = new MinHeap<Edge>(n * (n - 1) / 2); 
		int[] setNum = new int[n]; for (int i = 0; i < n; i++) 
		{ 
			setNum[i] = i; // 初始时，每个顶点是一个子集合 
		} // 初始化最小堆  
		for (int i = 0; i < n; i++) 
		{ 
			for (int j = i + 1; j < n; j++) 
			{
				if (isReachable(E, i, j)) 
			{ 
					edges.add(new Edge(i, j, E[i][j])); 
			} 
				} 
			} 
		Edge edge; 
		int count = n, v1, v2, num; 
		while ((count > 1) && (edge = edges.removeMin()) != null) 
		{ 
			v1 = edge.v1; v2 = edge.v2; 
			if (setNum[v1] == setNum[v2]) continue; // 两个顶点在同一个子集合里  
			count--; // 融合两个子集合，减少了一个子集合  
			num = setNum[v2]; for (int i = 0; i < n; i++) 
			{ 
				if (setNum[i] == num) { setNum[i] = setNum[v1]; // 把两个子集合融合到一个  
				} 
				}
			System.out.println((v1+1) + "~" + (v2+1) + " : " + edge.len); } } 
	  private static boolean isReachable(int[][] E, int v1, int v2) 
	  { 
		  return E[v1][v2] != NOT_REACHED; 
	  } 
	  public static void main(String[] args) 
	  { 
		  int[][] E = { { -1, 6, 1, 5, -1, -1 }, 
				  { 6, -1, 5, -1, 3, -1 }, 
				  { 1, 5, -1, 5, 6, 4 }, 
				  { 5, -1, 5, -1, -1, 2 }, 
				  { -1, 3, 6, -1, -1, 6 }, 
				  { -1, -1, 4, 2, 6, -1 } 
				  }; 
		  kruskal(E); 
		  } 
	  } 







